package com.javaDemo.ti;

import java.util.*;

/**
 * 常见算法题解析
 * 
 * @author csy
 * @description 面试中常见的算法题分类和详细解析
 * 
 *              算法题目分类：
 *              1. 数组
 *              2. 字符串
 *              3. 双指针
 *              4. 滑动窗口
 *              5. 二分查找
 * 
 *              解题思路要点：
 *              1. 理解问题的核心要求
 *              2. 分析可能的解决方案
 *              3. 考虑边界情况和特殊输入
 *              4. 优化时间和空间复杂度
 */
public class CommonAlgorithmExamples {

    /**
     * 【数组类】最长连续递增子序列
     * 
     * 问题描述：
     * 给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。
     * 
     * 解题思路：
     * 1. 为什么用一次遍历？
     * - 连续递增要求相邻元素必须递增
     * - 只需要比较当前元素和前一个元素
     * 
     * 2. 解题步骤：
     * a) 定义变量：
     * - currentLength：当前连续递增序列的长度
     * - maxLength：最长连续递增序列的长度
     * 
     * b) 遍历数组：
     * - 如果当前元素大于前一个元素，currentLength++
     * - 否则重置currentLength为1
     * - 更新maxLength
     * 
     * 3. 举例说明：
     * 输入：[1,3,5,4,7]
     * 遍历过程：
     * - 1 -> currentLength=1, maxLength=1
     * - 3 > 1 -> currentLength=2, maxLength=2
     * - 5 > 3 -> currentLength=3, maxLength=3
     * - 4 < 5 -> currentLength=1, maxLength=3
     * - 7 > 4 -> currentLength=2, maxLength=3
     * 
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     */
    public static int findLengthOfLCIS(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;

        int currentLength = 1;
        int maxLength = 1;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                currentLength++;
                maxLength = Math.max(maxLength, currentLength);
            } else {
                currentLength = 1;
            }
        }

        return maxLength;
    }

    /**
     * 【字符串类】最长回文子串
     * 
     * 问题描述：
     * 给定一个字符串s，找到s中最长的回文子串。
     * 
     * 解题思路：
     * 1. 为什么用中心扩展法？
     * - 回文串的特点是关于中心对称
     * - 可以从每个可能的中心向两边扩展
     * 
     * 2. 解题步骤：
     * a) 考虑两种情况：
     * - 奇数长度回文串，中心是一个字符
     * - 偶数长度回文串，中心是两个字符
     * 
     * b) 对每个中心位置：
     * - 向两边扩展，直到不满足回文条件
     * - 记录最长的回文子串
     * 
     * 3. 举例说明：
     * 输入："babad"
     * - 以'b'为中心：b
     * - 以'a'为中心：aba
     * - 以'b'为中心：bab
     * - 以'a'为中心：a
     * - 以'd'为中心：d
     * 最长回文子串：aba 或 bab
     * 
     * 时间复杂度：O(n²)
     * 空间复杂度：O(1)
     */
    public static String longestPalindrome(String s) {
        if (s == null || s.length() < 2)
            return s;

        int start = 0, maxLength = 1;

        for (int i = 0; i < s.length(); i++) {
            // 奇数长度回文串
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);

            int len = Math.max(len1, len2);
            if (len > maxLength) {
                start = i - (len - 1) / 2;
                maxLength = len;
            }
        }

        return s.substring(start, start + maxLength);
    }

    private static int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }

    /**
     * 【双指针类】盛最多水的容器
     * 
     * 问题描述：
     * 给定n个非负整数a1，a2，...，an，每个数代表坐标中的一个点(i, ai)。
     * 找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。
     * 
     * 解题思路：
     * 1. 为什么用双指针？
     * - 容器的水量由两个因素决定：两条线的距离和较短线的高度
     * - 可以通过双指针逐步排除不可能的情况
     * 
     * 2. 解题步骤：
     * a) 初始化：
     * - 左指针指向开始，右指针指向结束
     * - 记录最大面积
     * 
     * b) 移动策略：
     * - 计算当前面积
     * - 移动较短的那条线的指针
     * - 更新最大面积
     * 
     * 3. 举例说明：
     * 输入：[1,8,6,2,5,4,8,3,7]
     * - 初始：left=0, right=8
     * - 面积=min(1,7)*8=8
     * - 移动左指针（因为1更小）
     * - 继续类似过程...
     * 
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     */
    public static int maxArea(int[] height) {
        int maxArea = 0;
        int left = 0;
        int right = height.length - 1;

        while (left < right) {
            int width = right - left;
            int h = Math.min(height[left], height[right]);
            maxArea = Math.max(maxArea, width * h);

            // 移动较短的线
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;
    }

    /**
     * 【滑动窗口类】无重复字符的最长子串
     * 
     * 问题描述：
     * 给定一个字符串，找出其中不含有重复字符的最长子串的长度。
     * 
     * 解题思路：
     * 1. 为什么用滑动窗口？
     * - 需要动态维护一个不含重复字符的窗口
     * - 窗口的扩展和收缩可以通过双指针实现
     * 
     * 2. 解题步骤：
     * a) 初始化：
     * - 使用Set记录窗口中的字符
     * - 左右指针初始化为0
     * 
     * b) 窗口操作：
     * - 右指针扩展窗口直到遇到重复字符
     * - 左指针收缩窗口直到删除重复字符
     * - 更新最大长度
     * 
     * 3. 举例说明：
     * 输入："abcabcbb"
     * - 初始窗口：[]
     * - 扩展：[a,b,c]
     * - 遇到a，收缩：[b,c]
     * - 扩展：[b,c,a]
     * - 继续类似过程...
     * 
     * 时间复杂度：O(n)
     * 空间复杂度：O(min(m,n)) 其中m是字符集大小
     */
    public static int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int maxLength = 0;
        int left = 0;

        for (int right = 0; right < s.length(); right++) {
            while (set.contains(s.charAt(right))) {
                set.remove(s.charAt(left));
                left++;
            }
            set.add(s.charAt(right));
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }

    /**
     * 【二分查找类】搜索旋转排序数组
     * 
     * 问题描述：
     * 给定一个经过旋转的排序数组nums和一个目标值target，
     * 如果目标值存在返回其索引，否则返回-1。
     * 
     * 解题思路：
     * 1. 为什么用二分查找？
     * - 原数组是有序的，经过旋转后部分有序
     * - 可以利用有序部分进行二分查找
     * 
     * 2. 解题步骤：
     * a) 初始化：
     * - 左右指针指向数组两端
     * 
     * b) 二分策略：
     * - 找到中间点，判断哪半部分有序
     * - 判断target是否在有序部分范围内
     * - 根据判断结果选择区间
     * 
     * 3. 举例说明：
     * 输入：nums = [4,5,6,7,0,1,2], target = 0
     * - 中间元素7，右半部分有序
     * - 0在右半部分范围内
     * - 在右半部分继续查找
     * 
     * 时间复杂度：O(log n)
     * 空间复杂度：O(1)
     */
    public static int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            }

            // 左半部分有序
            if (nums[left] <= nums[mid]) {
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            // 右半部分有序
            else {
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return -1;
    }

    /**
     * 【单调栈类】接雨水
     * 
     * 问题描述：
     * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
     * 
     * 解题思路详解：
     * 1. 为什么用单调栈？
     * - 接雨水问题本质是找每个位置左右两侧第一个比自己高的柱子
     * - 单调栈可以在O(n)时间内找到每个元素左右两侧第一个比自己大的元素
     * - 单调栈特性：维护一个高度单调递减的栈，遇到更高元素时，栈顶元素找到了右边界
     * 
     * 2. 单调栈工作原理：
     * - 单调栈是指栈内元素保持单调性（递增或递减）的栈
     * - 本题中使用单调递减栈，栈中存储柱子的下标
     * - 当遍历到的柱子高度大于栈顶柱子高度时，说明找到了一个可以接水的凹槽
     * 
     * 3. 详细解题步骤：
     * a) 维护单调栈：
     * - 栈中存储下标，对应的高度保持单调递减
     * - 当遇到比栈顶元素高的柱子时，栈顶元素找到了右边界（当前柱子）
     * - 栈顶下面的元素（如果存在）是左边界
     * 
     * b) 计算接水量：
     * - 弹出栈顶元素作为接水区域的底部（凹槽的最低点）
     * - 新的栈顶是左边界，当前遍历到的柱子是右边界
     * - 水能达到的高度 = min(左边界高度, 右边界高度) - 底部高度
     * - 接水宽度 = 右边界下标 - 左边界下标 - 1
     * - 当前凹槽接水量 = 宽度 × 高度
     * 
     * 4. 举例详解：
     * 输入：[0,1,0,2,1,0,1,3,2,1,2,1]
     * 过程分析：
     * - 遍历到索引1(值为1)：入栈 [0,1]
     * - 遍历到索引2(值为0)：入栈 [0,1,2]
     * - 遍历到索引3(值为2)：
     * > 2 > height[2]=0，弹出2，此时栈为[0,1]
     * > 计算：左边界=1(值为1)，右边界=3(值为2)，底部=2(值为0)
     * > 宽度 = 3-1-1 = 1，高度 = min(1,2)-0 = 1
     * > 接水量 += 1×1 = 1
     * > 1 < 2，继续弹出1，此时栈为[0]
     * > 计算：左边界=0(值为0)，右边界=3(值为2)，底部=1(值为1)
     * > 宽度 = 3-0-1 = 2，高度 = min(0,2)-1 = -1 (负值不接水)
     * > 入栈3，此时栈为[0,3]
     * - 继续类似过程...
     * 
     * 5. 算法特点：
     * - 单调栈保证了我们能够找到每个位置左右两侧第一个比它高的柱子
     * - 每个柱子最多入栈出栈各一次，保证了O(n)的时间复杂度
     * - 空间复杂度取决于栈的大小，最坏情况下为O(n)
     * 
     * 时间复杂度：O(n) - 每个元素最多入栈出栈各一次
     * 空间复杂度：O(n) - 栈的大小
     */
    public static int trap(int[] height) {
        // 如果数组为空或长度小于3，无法接雨水，直接返回0
        // 原因：接水至少需要3个柱子形成凹槽（左边界、底部、右边界）
        if (height == null || height.length < 3) {
            return 0;
        }

        int totalWater = 0; // 总接水量，累加所有凹槽的水量
        Stack<Integer> stack = new Stack<>(); // 单调递减栈，存储柱子的下标（不是高度）

        // 遍历每个柱子，寻找可以接水的凹槽
        for (int current = 0; current < height.length; current++) {
            // 当栈不为空且当前柱子高度大于栈顶柱子高度时，形成了一个凹槽，可以接雨水
            // 注意这里是while循环，因为一个高柱子可能会找到多个凹槽
            while (!stack.isEmpty() && height[current] > height[stack.peek()]) {
                // 弹出栈顶元素，作为接水区域的底部（凹槽的最低点）
                int bottom = stack.pop();

                // 如果栈为空，说明左边没有边界了，无法形成凹槽接水
                // 这种情况发生在底部左侧没有比它高的柱子
                if (stack.isEmpty()) {
                    break;
                }

                // 计算左右边界
                // 左边界是新的栈顶（弹出bottom后的栈顶）
                int left = stack.peek();
                // 右边界是当前遍历到的柱子
                // 此时形成了一个凹槽：left(左边界) -> bottom(底部) -> current(右边界)

                // 计算凹槽的宽度：右边界下标 - 左边界下标 - 1
                // 减1是因为不包括左右边界柱子本身占据的位置
                int width = current - left - 1;

                // 计算凹槽可以接水的高度
                // 水面高度取决于左右边界的较小值（木桶效应）
                int boundaryHeight = Math.min(height[left], height[current]);
                // 实际接水高度 = 水面高度 - 底部高度
                int waterHeight = boundaryHeight - height[bottom];

                // 累加当前凹槽的接水量：宽度 × 高度
                totalWater += width * waterHeight;
            }

            // 将当前柱子的下标入栈，维护单调递减栈
            // 注意：入栈的是下标，而不是高度值
            stack.push(current);
        }

        return totalWater; // 返回总接水量
    }

    /**
     * 测试方法
     */
    public static void main(String[] args) {
        // 测试最长连续递增子序列
        System.out.println("=== 最长连续递增子序列测试 ===");
        int[] nums1 = { 1, 3, 5, 4, 7 };
        System.out.printf("输入数组：%s%n结果：%d%n%n",
                Arrays.toString(nums1), findLengthOfLCIS(nums1));

        // 测试最长回文子串
        System.out.println("=== 最长回文子串测试 ===");
        String s1 = "babad";
        System.out.printf("输入字符串：%s%n结果：%s%n%n",
                s1, longestPalindrome(s1));

        // 测试盛最多水的容器
        System.out.println("=== 盛最多水的容器测试 ===");
        int[] height = { 1, 8, 6, 2, 5, 4, 8, 3, 7 };
        System.out.printf("输入数组：%s%n结果：%d%n%n",
                Arrays.toString(height), maxArea(height));

        // 测试无重复字符的最长子串
        System.out.println("=== 无重复字符的最长子串测试 ===");
        String s2 = "abcabcbb";
        System.out.printf("输入字符串：%s%n结果：%d%n%n",
                s2, lengthOfLongestSubstring(s2));

        // 测试搜索旋转排序数组
        System.out.println("=== 搜索旋转排序数组测试 ===");
        int[] nums2 = { 4, 5, 6, 7, 0, 1, 2 };
        int target = 0;
        System.out.printf("输入数组：%s，目标值：%d%n结果：%d%n%n",
                Arrays.toString(nums2), target, search(nums2, target));

        // 测试接雨水
        System.out.println("=== 接雨水测试 ===");
        int[] trapHeight = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
        System.out.printf("输入数组：%s%n结果：%d%n",
                Arrays.toString(trapHeight), trap(trapHeight));
    }
}